#include <vector>
#include <queue>
#include <unordered_set>

using namespace std;

// 丑数 II
// 给你一个整数 n ，请你找出并返回第 n 个 丑数
// 丑数 就是只包含质因数 2、3 或 5 的正整数
// 测试链接 : https://leetcode.cn/problems/ugly-number-ii/

class Solution 
{
public:
    // 暴力，时间复杂度 O(N * logN)
    int nthUglyNumber1(int n) 
    {
        int nums[] = {2, 3, 5};
        unordered_set<long> s;
        priority_queue<long, vector<long>, greater<long>> pq;
        s.insert(1L);
        pq.push(1L);
        for(int i = 1; i <= n; ++i)
        {
            long x = pq.top();
            pq.pop();
            if(i == n) return x;
            for(int num : nums)
            {
                long t = num * x;
                if(!s.count(t))
                {
                    s.insert(t);
                    pq.push(t);
                }
            }
        }
        return -1;
    }

    // 动态规划，时间复杂度 O(N)
	// n 代表第 n 个丑数
    int nthUglyNumber2(int n) 
    {
        // dp 0 1 2 3 ... n
        //      1 2 3 ... ?
        vector<int> dp(n + 1);
        dp[1] = 1;
        int a, b, c, cur;
        for(int i = 2, i2 = 1, i3 = 1, i5 = 1; i <= n; ++i)
        {
            a = dp[i2] * 2;
            b = dp[i3] * 3;
            c = dp[i5] * 5;
            cur = min(a, min(b, c));
            if(cur == a) ++i2;
            if(cur == b) ++i3;
            if(cur == c) ++i5;
            dp[i] = cur;
        }
        return dp[n];
    }
};